home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / TEMP / GNU / bison / ShiftRedue < prev    next >
Text File  |  1995-06-28  |  3KB  |  95 lines
  1. Shift\/Reduce
  2. Previous: <Look-Ahead=>LookAhead> * Next: <Precedence=>Precedencf> * Up: <Algorithm=>Algorithm>
  3.  
  4. #Wrap on
  5. {fH3}Shift\/Reduce Conflicts{f}
  6.  
  7. Suppose we are parsing a language which has if-then and if-then-else
  8. statements, with a pair of rules like this:
  9.  
  10. #Wrap off
  11. #fCode
  12. if\_stmt:
  13.           IF expr THEN stmt
  14.         | IF expr THEN stmt ELSE stmt
  15.         ;
  16. #f
  17. #Wrap on
  18.  
  19. Here we assume that {fCode}IF{f}, {fCode}THEN{f} and {fCode}ELSE{f} are
  20. terminal symbols for specific keyword tokens.
  21.  
  22. When the {fCode}ELSE{f} token is read and becomes the look-ahead token, the
  23. contents of the stack (assuming the input is valid) are just right for
  24. reduction by the first rule.  But it is also legitimate to shift the
  25. {fCode}ELSE{f}, because that would lead to eventual reduction by the second
  26. rule.
  27.  
  28. This situation, where either a shift or a reduction would be valid, is
  29. called a {fUnderline}shift\/reduce conflict{f}.  Bison is designed to resolve
  30. these conflicts by choosing to shift, unless otherwise directed by
  31. operator precedence declarations.  To see the reason for this, let's
  32. contrast it with the other alternative.
  33.  
  34. Since the parser prefers to shift the {fCode}ELSE{f}, the result is to attach
  35. the else-clause to the innermost if-statement, making these two inputs
  36. equivalent:
  37.  
  38. #Wrap off
  39. #fCode
  40. if x then if y then win (); else lose;
  41.  
  42. if x then do; if y then win (); else lose; end;
  43. #f
  44. #Wrap on
  45.  
  46. But if the parser chose to reduce when possible rather than shift, the
  47. result would be to attach the else-clause to the outermost if-statement,
  48. making these two inputs equivalent:
  49.  
  50. #Wrap off
  51. #fCode
  52. if x then if y then win (); else lose;
  53.  
  54. if x then do; if y then win (); end; else lose;
  55. #f
  56. #Wrap on
  57.  
  58. The conflict exists because the grammar as written is ambiguous: either
  59. parsing of the simple nested if-statement is legitimate.  The established
  60. convention is that these ambiguities are resolved by attaching the
  61. else-clause to the innermost if-statement; this is what Bison accomplishes
  62. by choosing to shift rather than reduce.  (It would ideally be cleaner to
  63. write an unambiguous grammar, but that is very hard to do in this case.)
  64. This particular ambiguity was first encountered in the specifications of
  65. Algol 60 and is called the ``dangling {fCode}else{f}'' ambiguity.
  66.  
  67. To avoid warnings from Bison about predictable, legitimate shift\/reduce
  68. conflicts, use the {fCode}%expect {fStrong}n{f}{f} declaration.  There will be no
  69. warning as long as the number of shift\/reduce conflicts is exactly {fStrong}n{f}.
  70. \*Note <Expect Decl=>ExpectDecl>: Suppressing Conflict Warnings.
  71.  
  72. The definition of {fCode}if\_stmt{f} above is solely to blame for the
  73. conflict, but the conflict does not actually appear without additional
  74. rules.  Here is a complete Bison input file that actually manifests the
  75. conflict:
  76.  
  77. #Wrap off
  78. #fCode
  79. %token IF THEN ELSE variable
  80. %%
  81. stmt:     expr
  82.         | if\_stmt
  83.         ;
  84.  
  85. if\_stmt:
  86.           IF expr THEN stmt
  87.         | IF expr THEN stmt ELSE stmt
  88.         ;
  89.  
  90. expr:     variable
  91.         ;
  92. #f
  93. #Wrap on
  94.  
  95.